﻿#include "BinarySearchTree.h"

#include <string>

void Test1()
{
	key::BSTree<int> t;
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };

	for (const auto& e : a)
	{
		t.Insert(e);
	}
	t.InOrder();

	t.Insert(16);
	t.Insert(3);
	t.InOrder();

	t.Erase(8);
	t.InOrder();

	t.Erase(3);
	t.InOrder();
	cout << "***********************" << endl;

	for (const auto& e : a)
	{
		t.Erase(e);
		t.InOrder();
	}
}

void Test2()
{
	key_value::BSTree<string, string> dict;
	
	dict.Insert("left", "左边");
	dict.Insert("right", "右边");
	dict.Insert("insert", "插入");
	dict.Insert("string", "字符串");
#if 0
	string str;
	while (cin >> str)
	{
		auto ret = dict.Find(str);
		if (ret)
		{
			cout << ret->_key << "->" << ret->_val << endl;
		}
		else
		{
			cout << "未记录的单词" << endl;
		}
	}
#endif

#if 1
	key_value::BSTree<string, string> copy = dict;
	copy.InOrder();
#endif
}

void Test3()
{
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
	key_value::BSTree<string, int> countTree;

	for (const auto& str : arr)
	{
		// 先查找⽔果在不在搜索树中
		// 1、不在，说明⽔果第⼀次出现，则插⼊<⽔果, 1>
		// 2、在，则查找到的结点中⽔果对应的次数++
		//BSTreeNode<string, int>* ret = countTree.Find(str);
		auto ret = countTree.Find(str);
		if (ret == nullptr)
		{
			countTree.Insert(str, 1);
		}
		else
		{
			ret->_val++;
		}
	}
	countTree.InOrder();
}

int main()
{
	//Test1();
	//Test2();
	Test3();

	return 0;
}